use num_integer::Roots as _;

/// Check if an **odd number** is a prime
///
/// If n is even, the result is unspecified.
fn is_odd_prime(n: u64) -> bool {
    if n < 3 {
        return false;
    }

    debug_assert!(n % 2 == 1);

    let mut i = 3;
    let s = n.sqrt();
    while i <= s {
        if n % i == 0 {
            return false;
        }
        i += 2;
    }
    true
}

/// Check if a number is a perfect square.
fn is_square(n: u64) -> bool {
    if n.trailing_zeros() % 2 != 0 {
        return false;
    }

    let s = n.sqrt();
    s * s == n
}

pub fn is_valid_goldbach(n: u64) -> bool {
    debug_assert!(n % 2 == 1);

    let mut i = 3;
    while i < n {
        if is_odd_prime(i) && is_square((n - i) / 2) {
            return true;
        }
        i += 2;
    }

    false
}

pub fn goldbach_conjecture() -> u64 {
    let mut count = 0;
    let mut sum = 0;
    let mut n = 9;

    while count < 2 {
        if !is_valid_goldbach(n) {
            count += 1;
            sum += n;
        }

        n += 2;

        while is_odd_prime(n) {
            n += 2;
        }
    }

    sum
}
